package com.chl.sort.other;

/**
 * 快速排序 - 不稳定 
 * 
 * 核心：分组交换排序
 * 
 * @author 陈宏亮
 *
 */
public class Sort04Quick {
	static int[] arrs;

	public static void sort(int[] arrs) {
		Sort04Quick.arrs = arrs;
//		recurrenceSort(0, arrs.length - 1);
		iterationSort();
	}

	/**
	 * 递归法
	 * 
	 * @param arrs
	 * @param s
	 * @param e
	 */
	private static void recurrenceSort(int s, int e) {
		int i = s;
		int left = s;
		int right = e;
		do {
			if (i == left) {
				if (swap(i, right)) {
					i = right;
					left += 1;
				} else {
					right -= 1;
				}
			} else {
				if (swap(left, i)) {
					i = left;
					right -= 1;
				} else {
					left += 1;
				}
			}
		} while (left != right);
		if (s < i - 1) {
			recurrenceSort(s, i - 1);
		}
		if (e > i + 1) {
			recurrenceSort(i + 1, e);
		}
	}

	private static boolean swap(int i, int j) {
		int tmp;
		if (arrs[i] > arrs[j]) {
			tmp = arrs[j];
			arrs[j] = arrs[i];
			arrs[i] = tmp;
			return true;
		}

		return false;
	}

	private static void iterationSort() {
		Range[] stack = new Range[arrs.length];
		int p = 0;
		stack[p++] = new Range(0, arrs.length - 1);
		while (p > 0) {
			Range range = stack[--p];
			if (range.start >= range.end)
				continue;
			int mid = arrs[range.end];
			int left = range.start, right = range.end - 1;
			while (left < right) {
				while (arrs[left] < mid && left < right)
					left++;
				while (arrs[right] >= mid && left < right)
					right--;
				// System.out.println(left + "-" + right);
				if (left != right) {
					swaps(left, right);
				}
			}
			if (arrs[left] >= arrs[range.end])
				swaps(left, range.end);
			else
				left++;
//			Sort00Demo.print(arrs);
			stack[p++] = new Range(range.start, left - 1);
			stack[p++] = new Range(left + 1, range.end);
		}
	}

	private static void swaps(int i, int j) {
		int tmp = arrs[j];
		arrs[j] = arrs[i];
		arrs[i] = tmp;
	}

}

class Range {
	int start;
	int end;

	Range(int s, int e) {
		this.start = s;
		this.end = e;
	}
}
